/**
 * 
 */
package array.passed2;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author Michael
 * @since 01/06/2013
 * 
 */

/*
 * Given an array of integers, find two numbers such that they add up to a
 * specific target number.
 * 
 * The function twoSum should return indices of the two numbers such that they
 * add up to the target, where index1 must be less than index2. Please note that
 * your returned answers (both index1 and index2) are not zero-based.
 * 
 * You may assume that each input would have exactly one solution.
 * 
 * Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
 */
public class TwoSumAddingToGivenTarget {

	public static int[] twoSum(int[] numbers, int target) {
		return twoSum2Points(numbers, target);
	}

	// time O(nlogn), space O(1)
	public static int[] twoSum2Points(int[] numbers, int target) {
		assert (numbers != null);
		assert (numbers.length >= 2);

		int[] result = new int[2];

		HashMap<Integer, Integer> numbers2Indexes = new HashMap<Integer, Integer>();
		for (int i = 0; i < numbers.length; i++) {
			if (!numbers2Indexes.containsKey(numbers[i])) {
				numbers2Indexes.put(numbers[i], i + 1);
			} else {
				if (numbers[i] * 2 == target) {
					result[0] = numbers2Indexes.get(numbers[i]);
					result[1] = i + 1;
					return result;
				}
			}
		}

		Arrays.sort(numbers);

		int left = 0;
		int right = numbers.length - 1;
		while (left < right) {
			int sum = numbers[left] + numbers[right];
			if (sum > target) {
				right--;
			} else if (sum < target) {
				left++;
			} else {
				result[0] = numbers2Indexes.get(numbers[left]);
				result[1] = numbers2Indexes.get(numbers[right]);
				if (result[0] > result[1]) {
					int tmp = result[0];
					result[0] = result[1];
					result[1] = tmp;
				}
				break;
			}
		}
		return result;
	}

	public int[] twoSumSet(int[] numbers, int target) {
		assert (numbers != null);
		assert (numbers.length >= 2);

		int[] result = new int[2];
		HashMap<Integer, Integer> numbers2Indexes = new HashMap<Integer, Integer>();
		for (int i = 0; i < numbers.length; i++) {
			if (!numbers2Indexes.containsKey(numbers[i])) {
				numbers2Indexes.put(numbers[i], i + 1);
			} else if (numbers[i] * 2 == target) {
				result[0] = numbers2Indexes.get(numbers[i]);
				result[1] = i + 1;
				return result;
			}
		}

		HashSet<Integer> set = new HashSet<Integer>();
		for (int i = 0; i < numbers.length; i++) {
			if (set.contains(target - numbers[i])) {
				result[0] = i + 1;
				result[1] = numbers2Indexes.get(numbers[i]);
				if (result[0] > result[1]) {
					int tmp = result[0];
					result[0] = result[1];
					result[1] = tmp;
				}
			} else {
				set.add(numbers[i]);
			}
		}

		return result;
	}

	// O(nlog(n)), O(1)
	public static void findPairsBySort(int[] arr, int target) {
		assert (arr != null);
		if (arr.length < 2)
			return;

		Arrays.sort(arr);
		int left = 0;
		int right = arr.length - 1;
		while (left < right) {
			int sum = arr[left] + arr[right];
			if (sum == target) {
				System.out.printf("(%d + %d) = %d\n", arr[left], arr[right],
						target);
				++left;
				--right;
			} else if (sum < target) {
				++left;
			} else { // sum > target
				--right;
			}
		}
	}

	// O(n), O(n)
	public static void findPairsByHash(int[] arr, int target) {
		assert (arr != null);
		if (arr.length < 2)
			return;
		HashSet<Integer> set = new HashSet<Integer>(arr.length);
		for (int i = 0; i < arr.length; ++i) {
			if (set.contains(target - arr[i])) {
				System.out.printf("(%d + %d) = %d\n", arr[i], target - arr[i],
						target);
			} else {
				set.add(arr[i]);
			}
		}
	}

	/**
	 * 
	 */
	public TwoSumAddingToGivenTarget() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = CreateUtils.randIntArray(10, 10);
		int target = CreateUtils.randInt(15);
		PrintUtils.printArray(a);
		System.out.println(target);
		findPairsByHash(a, target);
		findPairsBySort(a, target);
	}
	
}
